#ifndef HEAP_SORT
#define HEAP_SORT
template<class Type>
inline void Swap(Type& a, Type&b){	
	Type temp = a;	a = b;	b = temp;
}

template<class Type,int Length>
void HeapSort(Type (&array) [Length] ){	
	for(int i = Length / 2 - 1 ; i >=0 ; --i) // Create Heap
		HeapAjust(array,Length,i);
	Swap( array[0] , array[Length - 1] );

	for(int i = Length - 2 ; i > 0 ; --i){
		HeapAjust(array,i+1,0);
		Swap( array[0] , array[i] );
	}
}

template<class Type>
void HeapAjust(Type array [] , int length , int root){
	int left = 2*root + 1, right = 2*root + 2;
	if (left >= length)return;
	int maxIndex = left; Type max = array[left];
	if(right < length && array[left] < array[right]){		
			maxIndex = right;
			max = array[right];	
	}
	if( array[root] >= array[maxIndex] )return;
	Swap(array[root],array[maxIndex] );
	HeapAjust(array,length,maxIndex);
}
#endif